package class71To80;

import java.io.*;
import java.util.Arrays;

// 完全背包模板
// 测试链接 : https://www.luogu.com.cn/problem/P1616
public class UnboundedKnapsack {

    public static int MAX_M = 10005;

    public static int MAX_T = 10000005;

    public static long[] dp = new long[MAX_T];

    public static int[] costs = new int[MAX_M];

    public static int[] values = new int[MAX_M];

    public static int m, t;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(System.out);
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            t = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            for (int i = 1; i <= m; i++) {
                in.nextToken();
                costs[i] = (int) in.nval;
                in.nextToken();
                values[i] = (int) in.nval;
            }
            out.println(solve1());
        }
        out.flush();
        out.close();
        br.close();
    }

    private static long solve1() {
        long[][] dp = new long[m + 1][t + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= costs[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - costs[i]] + values[i]);
                }
            }
        }
        return dp[m][t];
    }

    private static long solve2() {
        Arrays.fill(dp, 0, t + 1, 0);
        for (int i = 1; i <= m; i++) {
            for (int j = costs[i]; j <= t; j++) {
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }
        return dp[t];
    }
}
